<?php
/**
 * <https://y.st./>
 * Copyright © 2017 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Debugging',
	'<{subtitle}>' => 'Written in <span title="Programming 2">CS 1103</span> of <a href="http://www.uopeople.edu/">University of the People</a>, finalised on 2017-07-12',
	'<{copyright year}>' => '2017',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<p>
	First, I tried running the program without any debugging tools.
	My goal was to find the first infinite loop, then start debugging that with Eclipse&apos;s debugging tools.
	With all the infinite loops cleared up, I could better focus on the other errors.
	My old computer was weak, and infinite loops in Java and Eclipse would sometimes freeze the whole machine.
	My new machine, the one I&apos;m working on now, is weaker still, so I wanted the worst issues out of the way as soon as possible.
</p>
<p>
	However, the program was so buggy it raised errors before even starting.
	It wasn&apos;t possible to use the debugger to locate these problems, as the program wasn&apos;t able to compile and run.
	They needed to be debugged by hand.
	Lines 20, 21, and 22 each contained a type mismatch in the variable assignments.
	This was easily fixed by adding a typecast, <code>(int[])</code>, just after the assignment operator and before the method call.
	Next, Eclipse told me the loop starting on line 57 was dead code; it would never be executed.
	I stared at it a while, but couldn&apos;t figure out why the loop would never execute.
	I did notice another error though, which is that the function would return after checking the first value of the array, checking only that value.
	Fixing that, the error message about dead code went away.
	It seems Eclipse was confused and complaining about the wrong problem.
	With those two errors fixed, I was able to run the program to find the next spot to debug.
</p>
<p>
	Running the program, the output halted after the initial built-in sort.
	Thant meant that the first custom sorting algorithm, <code>bubbleSort()</code>, was non-terminating.
	I added a breakpoint to the beginning of each loop and one to the end of the innermost loop, and tried running the debugger.
	What I noticed was that <code>j</code> never incremented, but <code>i</code> was extending up beyond its intended limit.
	At first, I thought these to be two isolated incidents.
	The <code>j</code> loop was failing to execute and the <code>i</code> loop was failing to terminate.
	However, that wasn&apos;t the issue at all.
	The <code>j</code> loop was incrementing the <code>*wrong variable*</code>, and as a result, the <code>j</code> loop was never terminating.
	The <code>j</code> loop was incrementing <code>i</code>, which had the additional effect of making the <code>i</code> loop appear to be buggy as well.
	Fixing the <code>j</code> loop to increment <code>j</code> instead of <code>i</code> caused the loop to behave as intended.
	That seemed to be the only infinite loop in the code, so with that cleared up, I started debugging the methods in order.
</p>
<p>
	Next up was <code>selectionSort()</code>.
	This method terminated, but was producing different output than <code>java.util.Arrays.sort()</code> and <code>bubbleSort()</code>.
	Again, I added breakpoints to the beginning of each loop and to the end of the innermost loop.
	That wasn&apos;t really helping though, so I added another breakpoint to the end of the outermost loop as well.
	I ran through the program several times, thoroughly confused by what I was seeing.
	Eventually though, I noticed that the array to be sorted was randomly generated, so I wasn&apos;t looking at the same array every time.
	It helped to know that.
	On the next run, I saw that a <code>7</code> got marked as the highest value in the array, but a <code>10</code> was present in the array too.
	How did that happen?
	Something in the code was causing the ten to get overlooked.
	Taking a look at the conditional in which <code>positionOfMax</code> is set, I found the error.
	Or rather, the errors.
	First, the <code>for</code> loop there was setting the initial value of <code>i</code> to <code>1</code>.
	Real programming languages, such as Java, index from zero.
	Second, the value of <code>i</code> wasn&apos;t being used in the conditional at all.
	Instead, the hard-coded value <code>1</code> was being used.
	With both of those fixed, <code>selectionSort()</code> provided the same results as the previous two sorting methods.
</p>
<p>
	Lastly, it was time to take a look at <code>insertionSort()</code>.
	It appeared to give a sorted array, but with the wrong values included.
	I added breakpoints to the beginning and end of both of the loops.
	What I noticed was that the value was being copied into and out of <code>temp</code>, but the other value that needed to move wasn&apos;t going anywhere.
	This was causing one value to be cloned and another lost.
	The problem was caused by the fact that in the inner loop, <code>pos+1</code> is the spot to take the new value, but outside the inner loop, <code>pos</code> was being used instead.
	I changed <code>array[pos] = temp;</code> to <code>array[pos+1] = temp;</code>, and that cleared up the duplication problem.
	However, the method was no longer generating a perfectly-sorted array, at least not every time.
	Sometimes, the array would be perfectly sorted, but other times, one value would be inappropriately moved to the beginning of the array.
	The issue seemed to be that the first element was being treated differently than the others.
	The problem was that in the while loop&apos;s conditional, <code>pos &gt; 0</code> was used.
	If the value of <code>pos</code> was zero, the loop wouldn&apos;t execute, so the first element wasn&apos;t properly handled.
	Changing it to <code>pos &gt;= 0</code> (<code>pos &gt; -1</code> would be an even more fun solution), everything ran as intended.
	With that, the entire program behaved as it should and provided reasonable output.
</p>
END
);
